#include <iostream>
#include <cmath>
#include <iterator>
#include <vector>
#include <sstream>
#include <string>
#include <cstdlib>
#include <algorithm>
using namespace std;

bool is_prime(int);
int get_next_prime(int);
vector<int> find_factors(int, int);
string print_vector(vector<int>);

vector<int> primes;

int main(int argc, char** argv)
{
  primes.push_back(1);
  primes.push_back(2);
  primes.push_back(3);

  int max_number = 20;

  if (argc >= 2)
    max_number = atoi(argv[1]);

  for(int i = 1; i <= max_number; ++i)
    {
      if (is_prime(i))
	{
	  //cout << i << " = prime" << endl;
	  cout << i << " 5" << endl; 
	}
      else
	{
// 	  vector<int> factors = find_factors(i, 2);
// 	  //cout << i << " = " << print_vector(factors) << endl;
// 	  cout << i << " 0" << endl;
	}
    }
}

bool is_prime(int number)
{
  if (binary_search(primes.begin(), primes.end(), number))
    return true;

  int number_sqrt = int(sqrt(number));
  for (int i = 2; i <= number_sqrt; ++i)
    {
      if (number % i == 0)
	return false;
    }

  primes.push_back(number);  
  return true;
}

int get_next_prime(int current_prime)
{
  vector<int>::iterator it = find(primes.begin(), primes.end(), current_prime);

  if (it != primes.end() || it != primes.end() - 1)
    return *(++it);
  else
    {
      it = primes.end() - 1;
      for (int i = (*it) + 1;; ++i)
	if (is_prime(i))
	  return i;
    }
}

vector<int> find_factors(int number, int current_prime)
{

  vector<int> factors;

  if (number == 1)
    return factors;

  if (number % current_prime == 0)
    {
      factors.push_back(current_prime);
      int multiplier = number / current_prime;
      vector<int> multiplier_factors = find_factors(multiplier, current_prime);
      copy(multiplier_factors.begin(), multiplier_factors.end(), back_inserter(factors));
    }
  else
    {
      int next_prime = get_next_prime(current_prime);
      return find_factors(number, next_prime);
    }
  return factors;
}

string print_vector(vector<int> factors)
{
  stringstream ss;
  for (vector<int>::iterator it = factors.begin(); it != factors.end(); ++it)
    ss << *it << " x ";
  ss << "1";

  return ss.str();
}
